The present invention relates to data compression and, more particularly, to improved entropy coding of compressed data streams.
Digital video comprises individual images or frames that are displayed in rapid succession. Digital images are typically represented as an array of data expressing the intensities of a plurality of picture elements or pixels. Each pixel is a sample of the intensity of the image at a set of coordinates defined by a rectangular grid virtually overlaying the image. The analog signal obtained by sampling the image at the spatial coordinates of a pixel is quantized to a discrete value that is proportional to the amplitude of the intensity or luminosity of the sample. Typically, the data for a pixel comprises a value representing the intensities of a plurality of component or primary colors of the sample. The image can be reconstructed for viewing by xe2x80x9cinvertingxe2x80x9d the quantized discrete sample values to produce a plurality of colored dots mapped to coordinates corresponding to the pixel locations in the original image.
While representing an image as an array of discrete pixel values is useful for image processing, the quantity of raw data required to represent an image is formidable. For example, a VHS based video display comprises a 320xc3x97480 rectangular array of pixels and a high definition television (HDTV) image comprises a 1360xc3x971024 pixel array. If each color image pixel is represented by three bytes (8 bit color), approximately one-half megabyte (MB) is required to represent a single VHS based image and approximately four MBs is required for an HDTV image. A full length movie at VHS resolution would require approximately 100 gigabytes (GB) of data, far in excess of the seventeen GBs maximum capacity of a digital video disk (DVD). If digital image data were not compressed before storage or transmission, such large quantities of data would make digital video impractical for most applications.
Video compression standards and related compression techniques have been developed to reduce the quantities of data necessary for digital video to levels that make storage and transmission practical. These standards include the MPEG family of standards promulgated by Motion Picture Experts Group standards (e.g., (MPEG-2xe2x80x94video) ISO-13818-2, GENERIC CODING OF MOVING PICTURES AND ASSOCIATED AUDIO, International Standards Organization) and the H.26X family of standards developed or under development by the International Telecommunications Union (ITU) (e.g., ITU-T RECOMMENDATION 263, VERSION 2, Telecommunications Standardization Sector, International Telecommunications Union). Typically, the digital video compression techniques exploit similarities between pixels within an image, referred to as spatial or intraframe correlation, and similarities between successive video frames, referred to as temporal or interframe correlation, to compress the raw data describing the pixels of a video sequence.
A digital video compression system comprises an encoder for compressing the raw video data and a decoder (collectively, a codec) to reverse the encoding process and reconstruct the images in the video frames for display. Referring to FIG. 1, a digital video encoder 20 typically comprises some form of differential pulse code modulation (DPCM) encoder 22 (indicated by a bracket) that converts the data representing the pixels of a sequence of video frames 24 to a syntactical bitstream 23 of quantized transform coefficients 26 representing intracoded frames and differential frame content of intercoded frames, motion vectors 28 describing the displacement of content in interframe coded frames, and mode data 30 or instructions to the decoder concerning the nature of the data included in the bitstream 23.
The output 23 of the DPCM encoder 22 is typically input to an entropy encoder 32 that applies one or more lossless compression processes to further compress the bitstream before it is stored or transmitted to a decoder 34. The objective of entropy encoding is to reduce the symbols of the bit stream to only the minimum required to convey the information content of the bit stream. The entropy of a symbol in a source is a function of the probability of the symbol:
Ei=xe2x88x92log2pi 
where:
Ei=the entropy of the symbol i
pi=the probability that the symbol i will occur in the source
Entropy coding comprises modeling a bitstream to determine the probabilities of each possible symbol value and substitution of a codeword for a bit stream symbol according to the probability of the symbol in the model. The effectiveness of entropy coding in further compressing the bitstream is intimately connected to the probabilistic similarity between the bitstream output by the DPCM coder 22, which varies for each video sequence, and the model bitstream utilized in the design of the entropy code. Entropy coding includes processes such as run length coding where sequences or runs of repeating symbols are replaced by a number indicating the number of repetitions in the run, variable length coding, and arithmetic coding.
One of the most common entropy coding techniques for video coding purposes is variable length coding. In variable length coding, compression is achieved by assigning shorter codewords (i.e., short sequences of bits) to bit stream symbols with higher probabilities of occurrence and longer codewords to symbols with lesser probabilities. The codewords and associated symbols are typically organized in a look up table or code book for use by the decoder. If the average codeword length is less than the average symbol length, the bitstream will have been compressed. The simplest form of variable length coding utilizes a static code in which a single code is used to code the symbols of a particular bitstream syntax. While static variable length codes have the advantage of simplicity and may be implemented with custom circuitry for rapid coding and decoding, the effectiveness of a static code suffers when the probability distribution of symbols in the bitstream being coded differs from the probability distribution in the model bitstream on which the design of the code is based. Adaptive variable length coding models the code to the probability statistics of the specific bitstream being compressed and provides good compression performance over a range of source data, but is more complex than static variable length coding since both the encoder and the decoder must track the changes in the variable length code as it adapts to changing bitstream probabilities. However, the efficiency of variable length coding, either static or adaptive, in compressing a bitstream is limited by the nature of the coding process. The optimal length of a variable length codeword equals the entropy of the coded symbol. If a symbol has a probability exceeding 0.5, the optimal length of the codeword is less than one bit. However, variable length codewords must include an integral number of bits. Since a high probability symbol will be inefficiently coded by variable length coding, a bit stream that includes the symbol will be either inefficiently compressed or even expanded.
Arithmetic coding provides an alternative to variable length coding. With this method it is possible to exactly represent the probabilities for symbols in the model bitstream with the result that performance does not suffer when the bitstream includes a frequently occurring symbol. An arithmetic coder is capable of achieving near optimal compression regardless of the probabilities of the symbols, but the performance of a static arithmetic coder still suffers when the bitstream statistics vary from those of the model bitstream on which the coder is based. An adaptive arithmetic coder can adapt the code to the statistics for the bitstream being coded, but this requires modeling several bit streams and updating the encoder and decoder as the arithmetic coder adapts to the changing statistics. However, arithmetic coders are more complex than variable length coders and have limited error robustness. A mismatch between the arithmetic coder and decoder caused by a single error renders the remaining data useless and adaptive coders must be frequently reset to avoid data loss.
What is desired, therefore, is a method of entropy coding that is easily implemented and provides good performance when applied to a bitstream that may include a symbol with a high probability of occurrence.